type MonaOp<T, S> = (x: T) => S;
type BinOp<T, S> = (elem: T) => (acc: S) => S;
type Lazy<T> = () => T;
type LazyNumber = Lazy<number>;
type LazyMonaOp<T, S> = (x: Lazy<T>) => Lazy<S>;
type LazyBinOp<T, S> = (elem: Lazy<T>) => (acc: Lazy<S>) => Lazy<S>;
type List<T> = {
    head: Lazy<T>,
    tail: LazyList<T>
} | null
// 惰性求值版本的 List，其本身、首元素、尾 List 均是惰性求值
type LazyList<T> = Lazy<List<T>>

const lazy = <T>(x: T) => () => x;

// ❗️ 注意: 若函数返回值为 Lazy 类型，当该函数作为实参时，必须转化为 () => f() 方可惰性求值（避免无限递归）


const compose = <T1, T2, T3>(f: (x: T2) => T3, g: (y: T1) => T2) => {
    return (x: T1) => f(g(x))
}

// 从 first 开始，无限生成整数
function range(first: LazyNumber): LazyList<number> {
    return () => {
        const x = first();
        return {
            head: lazy(x),
            tail: range(lazy(x + 1))
        };
    }
}

// 将数组转化为 LazyList
function toList<T>(xs: T[]): LazyList<T> {
    return () => {
        if (xs.length === 0) {
            return null;
        }
        return {
            head: lazy(xs[0]),
            tail: toList(xs.slice(1))
        };
    }
}


// 打印 LazyList，一行一个元素
function printList<T>(xs: LazyList<T>) {
    let pair = xs();
    while (pair !== null) {
        console.log(pair.head());
        pair = pair.tail();
    }
}

// cons: <T>(x: Lazy<T>) => (ys: LazyList<T>) => LazyList<T>
// 生成以 x 为首元素，ys 为尾 List 的 LazyList
const cons = <T>(x: Lazy<T>) => (ys: LazyList<T>): LazyList<T> => {
    const a = x()
    if (a === null) {
        return () => null;
    }
    return () => {
        return {
            head: lazy(a),
            tail: ys
        }
    }
}

const map = <T, S>(f: LazyMonaOp<T, S>) => (xs: LazyList<T>): LazyList<S> => {
    const pair = xs();
    if (pair === null) {
        return () => null;
    }
    const x = pair.head;
    const l = pair.tail
    return cons(f(x))(
        () => map(f)(l)()
    )
}

// 生成 [x, 
//         f(x), f(f(x)), ...]
const repeat = <T>(f: LazyMonaOp<T, T>) => (x: Lazy<T>): LazyList<T> =>
    cons(x)(() =>
        repeat(f)(f(x))()
    );


function take<T>(n: LazyNumber, xs: LazyList<T>): LazyList<T> {
    return () => {
        let m = n();
        let pair = xs()
        if (m === 0) {
            return null
        }
        if (pair === null) {
            return null
        }
        return {
            head: pair.head,
            tail: take(lazy(m - 1), pair.tail)
        }
    }
}



// const sqrt = (eps: number) => (n: number): number => {
//     let x = 1.
//     let y = 2. * eps
//     while (true) {
//         if ((Math.abs(x - y) <= eps)) {
//             break
//         }
//         y = x;
//         x = (x + n / x) / 2
//     }
//     return x
// }
// 
// console.log(sqrt(0.001)(10) * sqrt(0.001)(10))


console.log("=========== repeat next")

const next = (n: LazyNumber) => (x: LazyNumber): LazyNumber => lazy((x() + n() / x()) / 2);



// repeat(f)(x) 返回一个无穷 List, [x, f(x), f(f(x)), ...]
// 首先求 z = f(x)
// 构造一个 LazyList，首元素为 x，尾 List 为 () => repeat(f)(z)
// 只有取尾 List 值时才再次调用 f，并且将 () => repeat(f)(z) 绑定到下一个尾 List
// const repeat = (f: LazyMonaOp<number>) => (x: LazyNumber): LazyList<number> => cons(x)(() => repeat(f)(f(x))())

printList(
    take(lazy(20),
        repeat(
            next(lazy(10)))(lazy(2))))

console.log("=========== sqrt")

const within = (eps: LazyNumber) => (xs: LazyList<number>): LazyNumber => {
    let pair = xs();
    if (pair == null) {
        console.log("[warn] got in impossible path");
        return lazy(0);
    }
    let x = pair.head();
    let t = pair.tail()
    if (t == null) {
        return lazy(x);
    }
    let y = t.head()
    if (Math.abs(x - y) <= eps()) {
        return lazy(y);
    }
    return within(eps)(pair.tail)
}

const sqrt = (a0: LazyNumber) => (eps: LazyNumber) => (n: LazyNumber) => within(eps)(repeat(next(n))(a0))

console.log(sqrt(lazy(2))(lazy(0.001))(lazy(10))())

console.log("===========relative sqrt")

const relative = (eps: LazyNumber) => (xs: LazyList<number>): LazyNumber => {
    const pair = xs()
    if (pair === null) {
        console.log("[warn] got in impossible path");
        return lazy(0);
    }
    const a = pair.head();
    const t = pair.tail();
    if (t === null) {
        return lazy(a);
    }
    const b = t.head()
    if (Math.abs(a - b) <= eps() * Math.abs(b)) {
        return lazy(b);
    }
    return relative(eps)(lazy(t))
}

const relativeSqrt = (a0: LazyNumber) => (eps: LazyNumber) => (n: LazyNumber): LazyNumber => {
    return relative(eps)(repeat(next(n))(a0))
}

console.log(relativeSqrt(lazy(2))(lazy(0.001))(lazy(10))())


console.log("=========== numberial differentiation")

// easyDiff(f)(x)(h)：f(x) 在 [x, x + h] 的导数
const easyDiff = (f: (a: LazyNumber) => LazyNumber) => (x: LazyNumber) => (h: LazyNumber): LazyNumber => {
    const y2 = f(lazy(x() + h()))
    const y1 = f(x)
    return lazy((y2() - y1()) / h())
}

// halve(x) = x / 2
const halve = (x: LazyNumber): LazyNumber => lazy(x() / 2);

// differentiate(h0)(f)(x)：f(x) 在 [x, x + delta] 的导数，delta 为 [h0, h0/2, h0/4, ...]
const differentiate = (h0: LazyNumber) => (f: (a: LazyNumber) => LazyNumber) => (x: LazyNumber): LazyList<number> => {
    return () => map<number, number>(easyDiff(f)(x))
        (() => repeat(halve)(h0)())
        ()
    // differentiate 执行瞬间，map 就会执行，关键在于 map 中是否立即执行了第二个函数
}

const derivative = (h0: LazyNumber) => (eps: LazyNumber) => (f: (a: LazyNumber) => LazyNumber) => (x: LazyNumber) => {
    return within(eps)(() => differentiate(h0)(f)(x)())
}

const f = (a: LazyNumber): LazyNumber => lazy(a() * a());

console.log(derivative(lazy(0.1))(lazy(0.001))(f)(lazy(1))())



console.log("================ better derivative: [WRONG]")
// answer: A
// error:  B*h*h
// a(i)   = A + B * (power(2, n)) * (power(h, n))
// a(i+1) = A + B * (power(h, n))
// A = (a(i+1) * power(2, n) - a(i)) / (power(2, n) - 1)

const elimError = (n: LazyNumber) => (xs: LazyList<number>): LazyList<number> => {
    const pair = xs();
    if (pair === null) {
        return () => null;
    }
    const a = pair.head()
    const tail = pair.tail()
    if (tail === null) {
        return () => null;
    }
    const b = tail.head();
    return cons(lazy(b * (Math.pow(2, n()) - a) / (Math.pow(2, n()) - 1)))(() => elimError(n)(() => tail)())
}



const round = (x: LazyNumber): LazyNumber => {
    return lazy(Math.round(x()))
}

const log2 = (x: LazyNumber): LazyNumber => {
    return lazy(Math.log2(x()))
}

const order = (xs: LazyList<number>): LazyNumber => {
    const pair = xs();
    if (pair === null) {
        console.log("invalid input for func `order`")
        return lazy(0)
    }
    const a = pair.head();
    const tail = pair.tail();
    if (tail === null) {
        console.log("invalid input for func `order`");
        return lazy(0);
    }
    const b = tail.head();
    const l = tail.tail();
    if (l === null) {
        console.log("invalid input for func `order`");
        return lazy(0);
    }
    const c = l.head();

    return round(log2(lazy((a - c) / (b - c) - 1)))
}

const improve = (xs: LazyList<number>): LazyList<number> => {
    return elimError(order(xs))(xs)
}

const betterDerivative = (h0: LazyNumber) => (eps: LazyNumber) => (f: (a: LazyNumber) => LazyNumber) => (x: LazyNumber): LazyNumber => {
    return within(eps)(
        improve(
            improve(
                improve(
                    differentiate(h0)(f)(x)
                )
            )

        )
    )
}

console.log(betterDerivative(lazy(2.))(lazy(0.001))(f)(lazy(1))())



console.log("================ super derivative: [WRONG]")

const second = (xs: LazyList<number>): LazyNumber => {
    const pair = xs();
    if (pair === null) {
        console.log("invalid input for func `order`");
        return () => 0;
    }
    const tail = pair.tail();
    if (tail === null) {
        console.log("invalid input for func `order`");
        return () => 0;
    }
    return tail.head;
}

const superr = (xs: LazyList<number>) => {
    return map(second)(repeat(improve)(xs))
}

const superDerivative = (h0: LazyNumber) => (eps: LazyNumber) => (f: (a: LazyNumber) => LazyNumber) => (x: LazyNumber): LazyNumber => {
    return within(eps)(superr(differentiate(h0)(f)(x)))
}

console.log(superDerivative(lazy(1.))(lazy(0.001))(f)(lazy(1))())


// numerical integration

const easyIntegrate = (f: (a: LazyNumber) => LazyNumber) => (a: LazyNumber) => (b: LazyNumber): LazyNumber => {
    return lazy((f(a)() + f(b)()) * (b() - a()) / 2)
}

type Pair<T, S> = {
    a: Lazy<T>,
    b: Lazy<S>
} | null


type LazyPair<T, S> = Lazy<Pair<T, S>>;

const pair = <T, S>(x: Lazy<T>) => (y: Lazy<S>): LazyPair<T, S> => {
    return () => {
        return {
            a: x,
            b: y
        }
    }
}

const addPair = (lp: LazyPair<number, number>): LazyNumber => {
    const p = lp();
    if (p === null) {
        console.log("invalid input for func `order`");
        return () => 0;
    }
    return lazy(p.a() + p.b());
}

const zip = <T, S>(xs: LazyList<T>) => (ys: LazyList<S>): LazyList<Pair<T, S>> => {
    const p1 = xs();
    const p2 = ys();
    if (p1 === null || p2 === null) {
        return () => null;
    }

    return cons(() => pair<T, S>(p1.head)(p2.head)())
        (zip<T, S>(p1.tail)(p2.tail))
}

const integrate = (f: (a: LazyNumber) => LazyNumber) => (a: LazyNumber) => (b: LazyNumber): LazyList<number> => {
    const mid = lazy((a() + b()) / 2);
    return cons(easyIntegrate(f)(a)(b))(
        map(addPair)
            (zip<number, number>(integrate(f)(a)(mid))
                (integrate(f)(mid)(b))
            )
    )
}


console.log("=============better integrate")

const integ = (f: (a: LazyNumber) => LazyNumber) => (a: LazyNumber) => (b: LazyNumber) => (fa: LazyNumber) => (fb: LazyNumber): LazyList<number> => {
    const m = lazy((a() + b()) / 2);
    const fm = f(m);

    return cons(lazy((fa() + fb()) * (b() - a()) / 2))
        (
            map(addPair)(
                zip<number, number>(integ(f)(a)(m)(fa)(fm))
                    (integ(f)(m)(b)(fm)(fb))
            )
        )
}


const betterIntegrate = (f: (a: LazyNumber) => LazyNumber) => (a: LazyNumber) => (b: LazyNumber) =>
    integ(f)(a)(b)(f(a))(f(b));


const betterIntegration = (eps: LazyNumber) => (f: (a: LazyNumber) => LazyNumber) => (a: LazyNumber) => (b: LazyNumber) => {
    return within(eps)(betterIntegrate(f)(a)(b))
}

const relativeIntegration = (eps: LazyNumber) => (f: (a: LazyNumber) => LazyNumber) => (a: LazyNumber) => (b: LazyNumber) => {
    return relative(eps)(betterIntegrate(f)(a)(b))
}

